package main

import (
	"fmt"
)

//动态规划:0ms 100%,1.9MB 27%,这个只能处理小数据量的
func cuttingRope(n int) int {
	dp := []int{}
	for m := 2; m <= n; m++ {
		if n%m == 0 {
			dp = append(dp, pow(n/m, m))
		} else {
			dp = append(dp, pow(n/m+1, n%m)*pow(n/m, m-n%m))
		}
		if m > 2 {
			if dp[m-2] < dp[m-3] {
				return int(dp[m-3])
			}
		}
	}
	return int(dp[len(dp)-1])
}

func pow(a, n int) int {
	res := a
	for i := 1; i < n; i++ {
		res *= a
	}
	return res
}

//n = ax  area = x^(a) =  x^(n/x) = (x^(1/x))^n,x = e时面积有最大值，x = 2:1.41,x = 3:1.44,所以尽可能都分成3份
//0ms 100%, 1.7MB 98%
func cuttingRope1(n int) int {
	if n < 4 {
		return n - 1
	}
	res := 1
	if n%3 == 0 {
		for i := 0; i < n/3; i++ {
			res *= 3
			res %= (1e9 + 7)
		}
	} else if n%3 == 1 {
		for i := 1; i < n/3; i++ {
			res *= 3
			res %= (1e9 + 7)
		}
		res *= 4
	} else {
		for i := 0; i < n/3; i++ {
			res *= 3
			res %= (1e9 + 7)
		}
		res *= 2
	}
	return res % (1e9 + 7)
}

func main() {
	fmt.Println(cuttingRope(2))
	fmt.Println(cuttingRope(8))
	fmt.Println(cuttingRope1(16))
	fmt.Println(cuttingRope1(120))
}
